#include <iostream>
#include <string>
#include <queue>

using namespace std;
// 定义需要的变量
const int N = 1010;
int n, k;
string grid[N];
const int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
int vis[N][N][15];
int dist[N][N];

struct Node {
    int x, y, k;
    Node(int xx, int yy, int kk) {
        x = xx;
        y = yy;
        k = kk;
    }
};

int bfs() {
    queue<Node> q;
    q.push({0, 0, 0});
    vis[0][0][0] = 1;
    while (q.size()) {
        auto node = q.front();
        q.pop();
        int x = node.x, y = node.y;
        if (x == n - 1 && y == n - 1) {
            return dist[x][y];
        }

        for (int i = 0; i < 4; ++i) {
            int xx = x + dir[i][0], yy = y + dir[i][1];
            if (xx < 0 || xx >= n || yy < 0 || yy >= n || grid[xx][yy] == '#') {
                continue;
            }
            if (grid[xx][yy] == '%' && !vis[xx][yy][k]) {
                q.push({xx, yy, k});
                dist[xx][yy] = dist[x][y] + 1;
                vis[xx][yy][k] = 1;
            } else {
                // 还有无敌状态
                if (node.k && !vis[xx][yy][node.k - 1]) {
                    q.push({xx, yy, node.k - 1});
                    dist[xx][yy] = dist[x][y] + 1;
                    vis[xx][yy][node.k - 1] = 1;
                } else if (!node.k && !vis[xx][yy][0] && grid[xx][yy] == '.') {
                    // 没有无敌状态并且前方路是通的
                    q.push({xx, yy, 0});
                    dist[xx][yy] = dist[x][y] + 1;
                    vis[xx][yy][0] = 1;
                }
            }
        }
    }

    return -1;
}

int main() {

    cin >> n >> k;

    for (int i = 0; i < n; ++i) {
        cin >> grid[i];
    }

    cout << bfs() << endl;

    return 0;
}